Đền Cô Tiên được xây dựng vào thời Lý theo kiểu kiến trúc cổ, gồm 3 lớp: Tiền Đường, Trung Đường và Hậu Cung. Kiểu kiến trúc hình chữ Đinh (hay kiến trúc chuôi vồ). Trải qua bao độ mưa nắng, gió bão và sự tàn phá của chiến tranh ngôi đền đã bị hư hỏng nặng. Ngôi đền đã qua nhiều lần trùng tu tôn tạo. Những năm 90 của thế kỷ XX, Ban quản lý di tích thành phố Sầm Sơn cho sửa chữa lại một số hạng mục. Lần tu sữa gần đây nhất vào năm 2010 Thành phố Sầm Sơn đã trùng tu tôn tạo lại toàn bộ ngôi đền nhưng vẫn giữ nguyên nét cổ kính. Kinh phí xây dựng Đền là từ nguồn tiền công đức của nhân dân và du khách thập phương.

Ngôi đền đã được xếp hạng Di Tích quốc gia năm 1962.

Ngoài Đền chính, trong quần thể Di Tích Đền Cô Tiên còn có đền trình(Quan Giám) Miếu lộ thiên Nam Hải Đại Vương, Miếu Cô Chín.